package com.peng.test.sort;

import java.util.Arrays;

/**
 * QuickSort
 * <p>
 * 快速排序, 归并排序
 *
 * @author: lupeng6
 * @create: 2020/12/10 11:44
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] arr = {10, 7, 2, 4, 7, 62, 3, 4, 2, 1, 8, 9, 19};
        new Solution().sort(arr, 0, arr.length - 1);
        Arrays.stream(arr).forEach(System.out::println);
    }


    static class Solution {
        public void sort(int[] arr, int low, int high) {
            if (low > high) {
                return;
            }
            int i, j, base, temp;
            i = low;
            j = high;
            base = arr[low];
            while (i < j) {
                while (base <= arr[j] && i < j) {
                    j--;
                }

                while (base >= arr[i] && i < j) {
                    i++;
                }

                if (i < j) {
                    temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }

            temp = arr[low];
            arr[low] = arr[j];
            arr[j] = temp;
            this.sort(arr, low, j - 1);
            this.sort(arr, j + 1, high);
        }
    }

}
